package com.ls.que91_95;

import com.ls.utils.TreeNode;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ：ls
 * @date ：2022/3/12 10:03
 * @description：...
 */
public class GenerateTrees {
    public List<TreeNode> generateTrees(int n) {
        if (n==0)
            return new ArrayList<TreeNode>();
        return gen(1,n);

    }
    public List<TreeNode> gen(int start, int end){
        List<TreeNode> allTree = new ArrayList<>();
        if (start > end){
            allTree.add(null);
            return allTree;
        }


        for (int i=start; i<=end; i++){
            List<TreeNode> leftTree = gen(start, i-1);
            List<TreeNode> rightTree = gen(i+1, end);
            for (TreeNode left : leftTree){
                for (TreeNode right : rightTree){
                    TreeNode r = new TreeNode(i);
                    r.left = left;
                    r.right = right;
                    allTree.add(r);
                }
            }
        }
        return allTree;
    }
}
